# 给你单链表的头结点 head ，请你找出并返回链表的中间结点。 
# 
#  如果有两个中间结点，则返回第二个中间结点。 
# 
#  
# 
#  示例 1： 
#  
#  
# 输入：head = [1,2,3,4,5]
# 输出：[3,4,5]
# 解释：链表只有一个中间结点，值为 3 。
#  
# 
#  示例 2： 
#  
#  
# 输入：head = [1,2,3,4,5,6]
# 输出：[4,5,6]
# 解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。
#  
# 
#  
# 
#  提示： 
# 
#  
#  链表的结点数范围是 [1, 100] 
#  1 <= Node.val <= 100 
#  
# 
#  Related Topics 链表 双指针 👍 1037 👎 0
from typing import Optional

from LeetCode.Test.LinkTool import ListNode, Link, LinkedListTool


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        root = ListNode(-1)
        root.next = head
        fast = root
        slow = root
        while True:
            # 偶数个节点
            if not fast.next:
                return slow.next
            # 奇数个节点
            if not fast.next.next:
                return slow.next
            fast = fast.next.next
            slow = slow.next


# leetcode submit region end(Prohibit modification and deletion)
Link.each(Solution().middleNode(LinkedListTool([1, 2, 3, 4, 5])))
